/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* gTail,*gHead,*lTail,*lHead;
    gHead=gTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    lHead=lTail=(struct ListNode*)malloc(sizeof(struct ListNode));
    gTail->next=lTail->next=NULL;
    struct ListNode *cur=head;
    while(cur)
    {
        if(cur->val<x)
        {
            lTail->next=cur;
            lTail=lTail->next;
        }
        else
        {
            gTail->next=cur;
            gTail=gTail->next;
        }
        cur=cur->next;
    }
    lTail->next=gHead->next;
    gTail->next=NULL;
    cur=lHead->next;
    return cur;
}